1. Field of the Invention
The present invention relates to a synchronous counter for use in a semiconductor integrated circuit such as MOS memory.
2. Description of the Prior Art
FIG. 4 is a circuit diagram illustrating a binary counter of a typical counter, and FIG. 5 is a circuit diagram illustrating a conventional synchronous counter using an LFSR. In FIGS. 4 and 5, F1-F8, F9-F16 each denote a flip-flop; E1-E7, E8-E10 each denote an exclusive OR circuit or EXOR gate; A1-A6 each denote an AND gate; and N1 denotes a NOT gate.
Here, a counter is constructed by n flip-flops (n: natural number), which repeat ON/OFF operations appropriately and come back to a primary status in a constant cycle. Though the n flip-flops take 2n states (n-th power of 2, nxe2x89xa70) at the maximum, a counter using the whole 2n states is a filled code counter, while a counter not using the 2n states all is an unfilled code counter. A representative of the filled code counter is a binary counter.
On the other hand, there is another classification for counters. That is, a counter provided with n flip-flops each having a class is a weighting counter, while a counter not having a class is a nonweighting counter. It is apparent that the binary counter belongs to the weighting counter, while a representative of the nonweighting counter is a Johnson counter.
An example of the nonweighting counter that takes 2nxe2x88x921 states and is infinitely in proximity with the filled code counter is an LFSR (Linear Feedback Shift Register). A shift register is as follows: A number of flip-flops are arranged in a line and the input and output of the neighboring flip-flops are connected with each other so as to be capable of reading the neighboring data. In addition, the LFSR is constructed to apply a feedback to the shift register by an operation circuit including an EXOR gate. There is an advantageous point that the entire circuit scale may be reduced when this LFSR is employed as the counter.
In the counter employing the LFSR, when a code of a state provided by the counter is considered as a vector, a code conversion to the next state may be considered as a linear map, which may be expressed by a matrix. This matrix is called expression matrix. Where the expression matrix is denoted by A (nxc3x97n matrix), a code of a current state is denoted by s (n-th vector), and a code of the next state s"" (n-th vector), these are expressed by the following relationship:
sxe2x80x2=Axc2x7sxe2x80x83xe2x80x83(1) 
The expression matrix A of this case is expressed by the following formula (2):                     A        =                  (                                                    0                                            1                                            0                                            ⋯                                            0                                            0                                                                                      xe2x80x83                                                            0                                            1                                            ⋯                                            0                                            0                                                                    ⋯                                            ⋯                                            ⋯                                                              xe2x80x83                                                            ⋯                                            ⋯                                                                    0                                            0                                            0                                            ⋯                                            1                                            0                                                                    0                                            0                                            0                                            ⋯                                            0                                            1                                                                                      a                  n                                                                              a                                      n                    -                    1                                                                                                a                                      n                    -                    2                                                                              ⋯                                                              a                  2                                                                              a                  1                                                              )                                    (        2        )            
A cycle of the counter corresponding to the expression matrix A is the minimum natural number m satisfying the following formula (3)
(Am)xc2x7s=sxe2x80x83xe2x80x83(3) 
It is known that the cycle of the expression matrix A is determined by its characteristic polynominal. When a cycle of one characteristic polynominal is the same as that of another, these characteristic polynominals are not always the same as each other. However, when one characteristic polynominal are the same as another, the cycles of these expression matrices are the same as each other. Note that the characteristic polynominal of the matrix A expressed by the formula (2) is "PHgr"(x)=xnxe2x88x92a1x(n-1)xe2x88x92 . . . xe2x88x92an-1xxe2x88x92an.
Further, by way of example, a conventional synchronous counter of FIG. 5 will be described below. This employs an LFSR of n=8. In FIG. 5, F9-F16 each denote a flip-flop; and E8-E10 each denote a 2-input EXOR gate. The outputs of the flip-flops F9-F15 are connected to the inputs of the flip-flops F10-F16, respectively. In addition, the outputs of the flip-flops F12 and F13 are connected to the inputs of the EXOR gate E9, and the outputs of the flip-flops F14 and F16 are connected to the inputs of the EXOR gate E10. Further, the outputs of the EXOR gates E9 and E10 are connected to the inputs of the EXOR gate E8, and the output of the EXOR gate E8 is connected to the input of the flip-flop F9.
The operation will be next described below.
Now, when the states of the flip-flops F16-F9 are respectively provided by (00000001) in a sequence of binary numbers, the next states of the flip-flops F16-F9 are transferred to (00000010), and the states after next thereof (00000100), respectively. The states of the flip-flops F16-F9 come back to (00000001) again after 255 clocks. Accordingly, the counter corresponds to a 255 counter.
Since the conventional synchronous counter by the LFSR is constructed as described above, it must employ the number of EXOR gates corresponding to the number of terms except the highest order of a characteristic polynominal. There is a problem that when the number of the terms is too large, the longest path which connects the output of one flip-flop with the input of another flip-flop, i.e. critical path, is lengthened.
For example, in the counter as shown in FIG. 5, the path from the output of the flip-flop F12 to the input of the flip-flop F9 corresponds to the critical path, of which the length corresponds to two stages of 2-input EXOR gates.
The present invention is implemented to solve the foregoing problems. It is therefor an object of the present invention to provide a synchronous counter having a short critical path with high speed and small scale.
According to a first aspect of the present invention, there is provided a synchronous counter comprising: at least three or more storage elements having a chain structure; and at least two or more 2-input logic gates interposed in the chain structure, wherein the number of stages of gates interposed between the output of one among the storage elements and the input of another among the storage elements is one stage of a 2-input logic gate even in the longest path.
According to a second aspect of the present invention, there is provided a synchronous counter comprising: a first storage element in which a first signal and a second signal are set to binary values via a set line and a control line, respectively; at least two or more second storage elements capable of setting the second signal to one value via the control line; and at least two or more 2-input logic gates interposed in a chain structure constructed by the first and second storage elements, wherein the number of stages of gates interposed between the output of one among the first and second storage elements and the input of another among the first and second storage elements is one stage of a 2-input logic gate even in the longest path.
Here, the 2-input logic may be constructed by a 2-input EXOR gate.